package Offer;
/*
    把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
    给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。
    例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。  
    注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */


/*
    思路：这题之前是做过类似的，就是二分的变体，进行一次二分，左半区或者右半区有一个是有序的，另外一个是部分有序
        要找到最小值，其实就是找到边界的值
        这个题，因为存在重复元素，所以处理就比较特殊（如果没有重复元素会比较简单一点点）

* */
public class T11_minArray {
    public int minArray(int[] numbers) {
        int start = 0, end = numbers.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (numbers[mid] > numbers[end]) {  //右边是无序的，存在最小值
                start = mid + 1;
            } else if (numbers[mid] < numbers[end]) { //右边是有序的，最小值只能是在左边
                end = mid;
            }else {
                //如果出现中间值和右边界元素相等的情况，那么不能保证右半区是有序的：
                //1) 如果右半区是无序的，那么最小值就在右半区；(eg: 4 4 4 3 4)
                //2) 如果右半区都是相同元素时（所有元素都是相等的，那么最小值应该在左半区找） (eg: 4 3 4 4 4)
                end --; //只需要让end指针右移，缩小查找的区间（下
                // 一轮循环会重置mid指针） 如果整个数组都是重复元素，那么就会一直end--直到第一个元素
            }
        }
        //当start==end时就找到了
        return numbers[start];
    }
}